//#pragma once
//#include<iostream>
//#include<assert.h>
//#include<algorithm>
//
//using namespace std;
//
//namespace yangyi
//{
//	template <class K>
//	struct BSTreeNode
//	{
//		K _key;
//		BSTreeNode<K>* _left;
//		BSTreeNode<K>* _right;
//
//		BSTreeNode(const K& key)
//			:_key(key)
//			,_left(nullptr)
//			,_right(nullptr)
//		{
//
//		}
//	};
//	template <class K>
//	class BSTree
//	{
//		typedef BSTreeNode<K> Node;
//	public:
//		bool Insert(const K& key)
//		{
//			if (_root == nullptr)
//			{
//				return false;
//			}
//			Node* parent = nullptr;
//			Node* cur = _root;
//			while (_root)
//			{
//				if (cur->_key < key)
//				{
//					parent = cur;
//					cur = cur->_right;
//				}
//				else if(cur->_key>key)
//				{
//					parent = cur;
//					cur = cur->_left;
//				}
//				else
//				{
//					return false;
//				}
//			}
//			cur = new Node(key);
//			if (parent->_left == cur)
//				parent->_left = cur;
//			else
//				parent->_right = cur;
//			return true;
//		}
//		bool Find(const K& key)
//		{
//			if (_root == nullptr)
//				return false;
//			Node* parent = nullptr;
//			Node* cur = _root;
//			while (cur)
//			{
//				if (cur->_key < key)
//				{
//					parent = cur;
//					cur = cur->_right;
//				}
//				else if (cur->_key > key)
//				{
//					parent = cur;
//					cur = cur->_left;
//				}
//				else
//				{
//					return true;
//				}
//			}
//			return false;
//		}
//		bool Erase(const K& key)
//		{
//			if (_root == nullptr)
//				return false;
//			Node* parent = cur;
//			Node* cur = _root;
//			while (cur)
//			{
//				if (cur->_key < key)
//				{
//					parent = cur;
//					cur = cur->_right;
//				}
//				else if (cur->_key > key)
//				{
//					parent = cur;
//					cur = cur->_left;
//				}
//				else
//				{
//					if (cur->_left == nullptr)
//					{
//						if (cur == _root)
//						{
//							_root = cur->_right;
//						}
//						else
//						{
//							if (parent->_left == cur)
//							{
//								parent->_left = cur->_right;
//
//							}
//							else
//							{
//								parent->_right = cur->_right;
//							}
//						}
//						delete cur;
//						cur = nullptr;
//					}
//					else if (cur->_right == nullptr)
//					{
//						if (_root == cur)
//						{
//							_root = cur->_left;
//						}
//						else
//						{
//							if (parent->_left == cur)
//							{
//								parent->_left = cur->_left;
//							}
//							else
//							{
//								parent->_right = cur->_left;
//							}
//						}
//						delete cur;
//						cur = nullptr;
//					}
//					else
//					{
//						Node* minParent = cur;
//						Node* min = cur->_right;
//						while (min->_left)
//						{
//							minParent = min;
//							min = min->_left;
//						}
//						swap(min->_key, cur->_key);
//						if (minParent->_left == min)
//							minParent->_left = min;
//						else
//							minParent->_right = min;
//						delete min;
//						return true;
//					}
//				}
//			}
//			return false;
//		}
//	private:
//		Node* _Copy(Node* root)
//		{
//			if (root == nullptr)
//				return nullptr;
//			Node* copyRoot = new Node(root->_key);
//			copyRoot->_left = _Copy(root->_left);
//			copyRoot->_right = _Copy(root->_right);
//			return copyRoot;
//		}
//		bool _InsertR(Node*& root,const K& key)
//		{
//			if (root == nullptr)
//			{
//				root = new Node(key);
//				return true;
//			}
//			if (root->_key < key)
//				return _InsertR(root->_right);
//			else if(root->_key>key)
//				return _InsertR(root->_left)
//			else
//			{
//				return false;
//			}
//		}
//		bool _EraseR(Node*& root, const K& key)
//		{
//			if (root == nullptr)
//			{
//				return false;
//			}
//			if (root->_key < key)
//				return _EraseR(root->_right, key);
//			else if (root->_key > key)
//				return _EraseR(root->_left, key);
//			else
//			{
//				Node* del = root;
//				if (root->_left == nullptr)
//					root = root->_right;
//				else if (root->_right == nullptr)
//					root = root->_left;
//				else
//				{
//					Node* min = root->_right;
//					while (min->_left)
//						min = min->_left;
//					swap(min->_key, root->_key);
//					return _EraseR(root->_right, key);
//				}
//				delete del;
//				return true;
//			}
//			return false;
//		}
//		bool _FindR(Node* root, const K& key)
//		{
//			if (root == nullptr)
//				return false;
//			if (root->_key < key)
//				return _FindR(root->_right, key);
//			else if (root->_key > key)
//				return _FindR(root->_left, key);
//			else
//			{
//				return true;
//			}
//		}
//		size_t _Height(Node* root)
//		{
//			if (root == nullptr)
//				return 0;
//			return max(_Height(root->_left), _Height(root->_right)) + 1;
//		}
//	private:
//		Node* _root = nullptr;
//	};
//}
//
//namespace yangyi2
//{
//	template <class K,class V>
//	struct RBTreeNode
//	{
//		pair<K, V> _kv;
//		RBTreeNode<K, V>* _left;
//		RBTreeNode<K, V>* _right;
//		RBTreeNode<K, V>* _parent;
//		size_t _bf;
//
//		RBTreeNode(const pair<K, V> kv)
//			:_kv(kv)
//			,_left(left)
//			,_right(right)
//			,_parent(parent)
//			_bf(0)
//		{
//
//		}
//	};
//
//	template <class K,class V>
//	class RBTree
//	{
//		typedef RBTreeNode<K, V> Node;
//	public:
//		bool Insert(const pair<K, V> kv)
//		{
//			if (_root == nullptr)
//			{
//				_root = new Node(kv);
//				return true;
//			}
//			Node* parent = nullptr;
//			Node* cur = _root;
//			while (cur)
//			{
//				if (cur->_kv.first < kv.first)
//				{
//					parent = cur;
//					cur = cur->_right;
//				}
//				else if (cur->_kv.first > kv.first)
//				{
//					parent = cur;
//					cur = cur->_left;
//				}
//				else
//				{
//					return false;
//				}
//			}
//			cur = new Node(kv);
//			if (parent->_left == cur)
//				parent->_left = cur;
//			else
//				parent->_right = cur;
//			cur->_parent = parent;
//			while (parent)
//			{
//				if (parent->_right == cur)
//					parent->_bf++;
//				else
//					parent->_bf--;
//				if (abs(parent->_bf) == 0)
//					break;
//				else if (abs(parent->_bf) == 1)
//				{
//					parent = parent->_parent;
//					cur = cur->_parent;
//				}
//				else if (abs(parent->_bf) == 2)
//				{
//					if (parent->_bf == 2 && cur->_bf == 1)
//						RotateL(parent);
//					else if (parent->_bf == -2 && cur->_bf == -1)
//						RotateR(parent);
//					else if (parent->_bf == -2 && cur->_bf == 1)
//						RotateLR(parent);
//					else if (parent->_bf == 2 && cur->_bf == -1)
//						RotateRL(parent);
//					else
//						break;
//				}
//				else
//					assert(false);
//			}
//		}
//	private:
//		void RotateL(Node* parent)
//		{
//			Node* subR = parent->_right;
//			Node* subRL = subR->_left;
//			parent->_right = subRL;
//			if (subRL)
//				subRL->_parent = parent;
//		
//			Node* ppNode = parent->_parent;
//			subR->_left = parent;
//			parent->_parent = subR;
//			if (ppNode == nullptr)
//			{
//				_root = subR;
//				subR->_parent = nullptr;
//			}
//			if (ppNode->_left == parent)
//				ppNode->_left = subR;
//			else
//				ppNode->_right = subR;
//			subR->_parent = ppNode;
//			subR->_bf = parent->_bf = 0;
//		}
//		void RotateLR(Node* parent)
//		{
//			Node* subL = parent->_left;
//			Node* subLR = subL->_right;
//			size_t bf = subLR->_bf;
//
//			RotateL(parent->_left);
//			RotateR(parent);
//			if (bf == 0)
//			{
//				parent->_bf = 0;
//				subL->_bf = 0;
//			}
//			else if (bf == -1)
//			{
//				parent->_bf = 1;
//				subL->_bf = 0;
//			}
//			else if (bf == 1)
//			{
//				parent->_bf = 0;
//				subL->_bf = -1;
//			}
//		}
//	private:
//		Node* _root = nullptr;
//	};
//}